The existence of simple, uncoupled no-regret dynamics that converge to correlated equilibria in normal-form games is a celebrated result in the theory of multi-agent systems. Specifically, it has been known for more than 20 years that when all players seek to minimize their internal regret in a repeated normal-form game, the empirical frequency of play converges to a normal-form correlated equilibrium. Extensive-form (that is, tree-form) games generalize normal-form games by modeling both sequential and simultaneous moves, as well as private information. Because of the sequential nature and presence of partial information in the game, extensive-form correlation has significantly different properties than the normal-form counterpart, many of which are still open research directions. Extensive-form correlated equilibrium (EFCE) has been proposed as the natural extensive-form counterpart to normal-form correlated equilibrium.

In the former, the mediator draws and recommends a complete normal-form plan to each player before the game starts. This is beneficial when the mediator wants to maximize, e.g., the Appendix A.1 provides a suitable formal definition of the set of EFCEs via the notion of trigger agent (originally This holds for arbitrary EFGs with multiple players and/or chance moves. Unfortunately, that algorithm is mainly a theoretical tool, and it is known to have limited scalability beyond toy problems. However, their algorithm is centralized and based on MCMC sampling which may limit its practical appeal. B.1 Proofs for Section 4 The following auxiliary result is exploited in the proof of Theorem 1. Lemma 4. This concludes the proof.Theorem 1.

Summary and Contributions: The authors provide a regret-minimisation approach to computing an analogue to correlated equilibria in extensive form games called extensive-form correlated equilibria (EFCE). It was previously unknown whether EFCE can be achieved via uncoupled no-regret dynamics as in typical correlated equilibria in simultaneous games, and the authors provide a way of doing so by introducing an appropriate notion of regret in the extensive form setting (that lines up with the notion of approximation in approximate EFCE), and demonstrating how achieving low regret in this setting suffices to have an approximate EFCE for joint strategy profiles that arise from empirical frequencies of play. As mentioned before, the relevant notion of equilibrium in this setting are extensive-form correlated equilibria (EFCE). Such an equilibrium is a joint distribution over the space of all possible plans of all agents. As is typical in an extensive-form setting, a plan is simply a mapping from information sets to their relevant action profiles that dictates what an agent does at any given situation of play. In the simultaneous setting, a mixed strategy profile is a correlated equilibrium when no agent wishes to deviate from the joint strategy profile, conditional on their realised strategy profile and prior knowledge of the joint distribution of play.

The existence of simple, uncoupled no-regret dynamics that converge to correlated equilibria in normal-form games is a celebrated result in the theory of multi-agent systems. Specifically, it has been known for more than 20 years that when all players seek to minimize their internal regret in a repeated normal-form game, the empirical frequency of play converges to a normal-form correlated equilibrium. Extensive-form (that is, tree-form) games generalize normal-form games by modeling both sequential and simultaneous moves, as well as private information. Because of the sequential nature and presence of partial information in the game, extensive-form correlation has significantly different properties than the normal-form counterpart, many of which are still open research directions. Extensive-form correlated equilibrium (EFCE) has been proposed as the natural extensive-form counterpart to normal-form correlated equilibrium.

Simple adaptive procedures that converge to correlated equilibria are known to exist for normal form games (Hart and Mas-Colell 2000), but no such analogue exists for extensive-form games. Leveraging inspiration from Zinkevich et al. (2008), we show that any internal regret minimization procedure designed for normal-form games can be efficiently extended to finite extensive-form games of perfect recall. Our procedure converges to the set of forgiving correlated equilibria, a refinement of various other proposed extensions of the correlated equilibrium solution concept to extensive-form games (Forges 1986a; Forges 1986b; von Stengel and Forges 2008). In a forgiving correlated equilibrium, players receive move recommendations only upon reaching the relevant information set instead of all at once at the beginning of the game. Assuming all other players follow their recommendations, each player is incentivized to follow her recommendations regardless of whether she has done so at previous infosets. The resulting procedure is completely decentralized: players need neither knowledge of their opponents' actions nor even a complete understanding of the game itself beyond their own payoffs and strategies.